#include "linklist.h"
#include<stdio.h>
#include<stdlib.h>

// 初始化空链表（不带头节点） head --> NULL
linklist init_list(void)
{
    return NULL;
}

// 单循环链表的新节点
linklist new_node(int data)
{
    linklist new;

    new = malloc(sizeof(listnode));
    if(new != NULL)
    {
        new->data = data;
        new->next = new; // 形成单节点的循环链表
    }
    else
        perror("新建节点失败");

    return new;
}


// 尾插法新增节点
// 返回新链表的头指针 head --> ... ... --> NULL
linklist list_add_tail(linklist head, linklist new)
{
    // 特殊情况：空链表时new就是唯一的节点
    if(head == NULL)
    {
        return new;
    }

    // 一般情况
    // ① 找到尾节点指针tail
    linklist tail;
    for(tail=head; tail->next!=head; tail=tail->next);

    // ②
    tail->next = new;

    // ③
    new->next = head;
    return head;
}


// 遍历
void show_list(linklist head)
{
    linklist p;
    for(p=head; p->next!=head; p=p->next)
    {
        printf("%d\t", p->data);
    }
    printf("%d\n", p->data);
}

// 将指定节点剔除出链表
// 返回head的下一个节点指针
linklist list_del(linklist head)
{
    linklist p = head->next->next->next;
    free(head->next->next);
    head->next->next = p;
    return p;
}

// 约瑟夫游戏
// 返回仅剩1-2个幸运节点
linklist Josephus(linklist head)
{
    linklist p = head;
    while(p->next->next != p){
        p = list_del(p);
    }
    return p;
}